package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 完全二叉树的节点个数
 * @date 2025/4/12 13:41
 */
public class CountNodes_222 {

    /**
     * 参考dmsxl解法：dfs-后序
     * <p>
     * 思路：利用完全二叉树和满二叉树特性。
     * <p>
     * 分析：
     * <p>
     * 1.完全二叉树只有两种情况：要么是满二叉树；要么只是完全二叉树，其叶子节点出现在倒数第一层，或者倒数一二层都有（最后一层没满），但一定先有左孩子才有右孩子。
     * 2.对于情形一，满二叉树的节点总数 = 2^h - 1，其中h是高度；若一棵树只有一个节点，该树也是满二叉树；而情形二，就要到分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
     * 3.所以，此题可以转为，求每个满二叉树子树的节点个数的总和；叶子节点一定是满二叉树，所以递归不会进入死循环。
     * <p>
     * 为什么不转为，求最后一层节点数，倒数第二层及其以上通过公式2^h - 1计算？
     * ——完全二叉树的倒数第一层、倒数第二层可能都没铺满节点，其倒数第三层及其以上才是满二叉树。
     * <p>
     * 为什么leftDepth、rightDepth初始为0？
     * ——首先，leftDepth是当前节点node的最左孩子深度，另外2<<n = 2^n。
     * <p>
     * 如何判断为满二叉树？
     * ——对于一颗完全二叉树，其任一子树都是完全二叉树；若某个子树的左右孩子深度相同，还不一定是满二叉树，因为可能有左无右孩子；但是左右子树，分别一直向左、向右递归统计深度，如果相同则一定是满二叉树，原因也是完全二叉树是先有左才有右。
     * <p>
     * 为什么right一直向右边递归，当出现leftDepth == rightDepth，一定是满二叉树？
     * ——因为，首先root是完全二叉树，一定是先有左孩子才有右孩子，所以当节点的最左和最右的深度相等时，一定是满二叉树。
     * <p>
     * 复杂度：
     * 1.T(n) = O(log n × log n)
     * 2.S(n) = O(log n)
     */
    public int countNodes3(TreeNode root) {
        return getNodeNum(root);
    }

    public int getNodeNum(TreeNode node) {
        if (node == null) return 0;
        // 分别记录node最左和最右孩子的深度（不是简单的左、右子树深度），用于判断node是否为满二叉树
        TreeNode left = node.left;
        TreeNode right = node.right;
        int leftDepth = 0, rightDepth = 0;
        while (left != null) {
            leftDepth++;
            left = left.left;
        }
        while (right != null) {
            rightDepth++;
            right = right.right;
        }
        // node是满二叉树，则直接根据公式计算node的总节点数
        if (leftDepth == rightDepth) {
            // 相当于 2^leftDepth - 1
            return (2 << leftDepth) - 1;
        }

        // 当前节点node不是满二叉树，继续向下递归求node树的总节点数量
        // 左
        int leftNodes = getNodeNum(node.left);
        // 右
        int rightNodes = getNodeNum(node.right);

        // 中（+1是把当前节点node记录上）
        return leftNodes + rightNodes + 1;
    }

    /**
     * bfs
     * <p>
     * 该做法和下面的dfs-先序，这两种解法都没用到完全二叉树的特点，相当于当作普通二叉树来做。
     * 可参考dmsxl、官解的解法优化
     */
    public int countNodes2(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            ans += levelSize;
            for (int i = 0; i < levelSize; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
        }
        return ans;
    }

    /**
     * dfs-先序
     */
    int ans = 0;

    public int countNodes(TreeNode root) {
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode node) {
        if (node == null) return;

        ans++;
        dfs(node.left);
        dfs(node.right);
    }

}
